//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-20

public class P021_二叉树的最小深度_深度优先 {

    public static void main(String[] args) {
        Tree node7 = new Tree(7,null,null);
        Tree node6 = new Tree(6,node7,null);
        Tree node5 = new Tree(5,null,null);
        Tree node4 = new Tree(4,null,null);
        Tree node3 = new Tree(3,node6,null);
        Tree node2 = new Tree(2,node4,node5);
        Tree node1 = new Tree(1,node2,node3);
        System.out.println(fun(node1));
    }

    private static int fun(Tree root) {
        fun(root,1);
        return mind;
    }

    static int mind = Integer.MAX_VALUE;
    private static void fun(Tree root,int d) {
        if (root == null) return;
        //深度，叶子节点经历过的结点数，因此只需要在叶子节点比较谁的路径最短
        if (root.left == null && root.right == null) {
            mind = Math.min(mind,d);
            return;
        }
        fun(root.left,d+1);
        fun(root.right,d+1);
    }


    static class Tree {
        int val;
        Tree left;
        Tree right;

        public Tree(int val, Tree left, Tree right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
